#include <util.h>
#include <lsort.h>

int count_sort(int a[], int b[], int n, int k)
{
    int i, j;
    int *c;
    
    if (!a || !b || n <= 0 || k < 0)
	return -1;

    // elements between [0, k]
    c = (int *)malloc(sizeof(int) * (k+1));
    if (c == NULL)
	return -1;

    for (i = 0; i <= k; i++)
	c[i] = 0;
    for (i = 0; i < n; i++)
    { // now c[i] holds the number of elements which are
	// equal to i
	c[a[i]]++;
    }
#if 1
    // stable version
    for (i = 1; i <=k; i++)
    {
	// now c[i] holds the number of elements which are
	// equal to or less than i
	c[i] += c[i-1];
    }

    for (i = n-1; i >= 0; i--)
    {
	// NOTE: c[a[i]]-1 is necessary here since we store 
	// element from b[0]
	// let i from n-1 to 0 rather than from 0 to n-1,
	// means we want a stable sort algorithm.
	b[c[a[i]] - 1] = a[i];
	c[a[i]]--;  /* next element position with the same value with a[i]*/
    }
#else
    // unstable version
    // how to fill b: 
    // c[i] stands for the number of consecutive i in output array, 
    // and the sum of greater-than-zero c[i] is n. So, just
    // fill b with c[i](>0) consecutive i, in order, and let i from 0 to k.
    //  
    for ( i = j = 0; i <= k && j < n; c[i] > 0 ? b[j++] = i, c[i]-- : i++)
	;

#endif

    free (c);

    return 0;
}

// sort an n-element array of int, d-bit width at most.
int radix_sort(int a[], int n, int d)
{
    return 0;
}
